W6. Logic, Discrete Mathematics, Proof Techniques, Direct Proof, Contradiction, Induction

Author

Zakhar Podyakov

Published

October 7, 2025

Quiz | Flashcards

1. Summary

1.1 Introduction to Mathematical Proofs

A mathematical proof is a formal argument that demonstrates the truth of a mathematical statement. Proofs are constructed from a series of logical steps, starting from a set of assumptions (premises or axioms) and leading to a conclusion. Understanding proof techniques is fundamental to mathematics and computer science, as it provides the basis for verifying the correctness of algorithms and theorems.

1.2 Syntax and Logical Operations

To build proofs, we use a formal language with specific syntax.

1.2.1 Symbols and Quantifiers
  • Symbols: We use letters like \(A, B, C, ..., x, y, z\) to represent propositions or variables. These can also be indexed, such as \(A_1, B_{1,2}, x^1\).
  • Quantifiers: These symbols allow us to make statements about the scope of variables.
    • Universal Quantifier (\(\forall\)): Represents “for all” or “for every.” The statement \(\forall x P(x)\) means that the property \(P(x)\) is true for every possible value of \(x\) in a given domain.
    • Existential Quantifier (\(\exists\)): Represents “there exists.” The statement \(\exists x P(x)\) means that there is at least one value of \(x\) for which the property \(P(x)\) is true.
1.2.2 Logic Operations
  • Negation (\(\neg P\)): “not P”. It inverts the truth value of a proposition.
  • Conjunction (\(P_1 \& P_2\)): “\(P_1\) and \(P_2\)”. It is true only if both propositions are true.
  • Disjunction (\(P_1 \lor P_2\)): “\(P_1\) or \(P_2\)”. It is true if at least one of the propositions is true.
  • Implication (\(P_1 \to P_2\)): “if \(P_1\) then \(P_2\)”. It is false only when \(P_1\) is true and \(P_2\) is false.
  • Equivalence (\(P_1 \leftrightarrow P_2\)): “\(P_1\) if and only if \(P_2\)”. It is true if both propositions have the same truth value.
1.3 Theorems and Conditional Statements

A theorem is a statement that has been proven to be true. Many theorems are structured as conditional statements.

1.3.1 Implication: \(A \to B\)

In an implication, we distinguish between the roles of \(A\) and \(B\).

  • Sufficient Condition: \(A\) is a sufficient condition for \(B\). This means that if \(A\) is true, it is enough to guarantee that \(B\) is also true. For example, “being divisible by 6” is a sufficient condition for “being divisible by 3.”
  • Necessary Condition: \(B\) is a necessary condition for \(A\). This means that \(A\) cannot be true unless \(B\) is also true. “Being divisible by 3” is a necessary condition for “being divisible by 6.”
  • Contrapositive: Every implication \(A \to B\) is logically equivalent to its contrapositive, \(\neg B \to \neg A\). Proving one is the same as proving the other.
1.3.2 Conjunction in Hypotheses: \((A_1 \& A_2 \& \dots \& A_n) \to B\)

Sometimes, a conclusion \(B\) requires multiple conditions to be true simultaneously. In this case, \(A_1, A_2, \dots, A_n\) are collectively called the sufficient conditions for \(B\). For instance, “a line \(l_1\) is parallel to \(l_3\)” AND “a line \(l_2\) is parallel to \(l_3\)” are sufficient conditions to conclude that “\(l_1\) is parallel to \(l_2\).”

1.3.3 Equivalence: \(A \leftrightarrow B\)

An equivalence, often stated as “\(A\) if and only if \(B\),” means that \(A\) and \(B\) are logically interchangeable.

  • \(A\) is a sufficient and necessary condition for \(B\).
  • To prove \(A \leftrightarrow B\), we must prove two separate implications: \(A \to B\) (“only if” part) and \(B \to A\) (“if” part).
1.4 Basic Proof Techniques

An argument is a sequence of statements (premises) that logically lead to a final statement (the conclusion). We use various techniques to construct valid arguments.

1.4.1 Deduction vs. Induction
  • Deduction: A top-down approach that moves from general principles to a specific conclusion. If the premises are true, the conclusion must be true.
    • Analogy: All swans are white (premise). Daisy is a swan (premise). Therefore, Daisy is white (conclusion).
  • Induction: A bottom-up approach that moves from specific observations to a general conclusion. The conclusion is likely true but not guaranteed.
    • Analogy: Daisy is a swan and is white. Danny is a swan and is white. Dante is a swan and is white. Therefore, all swans are white.
1.4.2 Direct Proof

This is the most straightforward technique for proving an implication \(P \to Q\).

  1. Assume the premise \(P\) is true.
  2. Use definitions, axioms, and previously proven theorems to construct a logical chain of steps that leads directly to the conclusion \(Q\).
  3. Conclude that \(Q\) must be true.

This method relies on Rules of Inference, which are patterns of logical deduction.

  • Modus Ponens: If we know \(P\) is true and \(P \to Q\) is true, we can conclude \(Q\) is true.
  • Hypothetical Syllogism: If \(P \to Q\) and \(Q \to R\), then we can conclude \(P \to R\).
  • Universal Instantiation: From \(\forall x P(x)\), we can conclude \(P(c)\) for any specific element \(c\).
  • Existential Generalization: From \(P(c)\) for some element \(c\), we can conclude \(\exists x P(x)\).
1.4.3 Proof by Contradiction

This is an indirect proof technique used to prove a statement \(Q\) (or an implication \(P \to Q\)).

  1. Assume the opposite of what you want to prove is true. To prove \(P \to Q\), you assume \(P\) is true and \(\neg Q\) is true.
  2. Use these assumptions to derive a logical contradiction—a statement that is always false (e.g., \(X \& \neg X\)).
  3. Conclude that the initial assumption must have been false, and therefore the original statement must be true. A classic example is the proof that \(\sqrt{2}\) is irrational.
1.4.4 Proof by Mathematical Induction

This is a powerful technique used to prove that a statement \(P(n)\) is true for all integers \(n\) greater than or equal to some starting integer \(n_0\). It is a formalized version of inductive reasoning that provides deductive certainty.

  • Simple Induction:
    1. Basis Step: Prove that the statement \(P(n_0)\) is true for the initial value \(n_0\).
    2. Inductive Hypothesis: Assume that \(P(k)\) is true for an arbitrary integer \(k \ge n_0\).
    3. Inductive Step: Prove that the statement \(P(k+1)\) must also be true, using the inductive hypothesis.
    4. Conclusion: By the Principle of Mathematical Induction, \(P(n)\) is true for all integers \(n \ge n_0\).
  • Strong Induction:
    1. Basis Step: Prove the statement is true for the first few cases, \(P(n_0), P(n_0+1), \dots, P(n_0+m)\).
    2. Inductive Hypothesis: Assume that \(P(i)\) is true for all integers \(i\) from \(n_0\) up to an arbitrary integer \(k\) (i.e., for \(n_0 \le i \le k\)).
    3. Inductive Step: Prove that \(P(k+1)\) must be true, using the hypothesis that all previous statements are true.

2. Definitions

  • Argument: A sequence of propositions where the initial propositions (premises) are intended to support the final proposition (conclusion).
  • Premise: A statement in an argument that is assumed to be true for the purpose of proving a conclusion.
  • Conclusion: The final proposition in an argument, which is asserted to be true on the basis of the premises.
  • Theorem: A mathematical statement that has been proven to be true.
  • Sufficient Condition: In an implication \(A \to B\), \(A\) is a sufficient condition for \(B\). Its truth guarantees the truth of \(B\).
  • Necessary Condition: In an implication \(A \to B\), \(B\) is a necessary condition for \(A\). \(A\) cannot be true unless \(B\) is also true.
  • Contrapositive: The contrapositive of the statement \(A \to B\) is \(\neg B \to \neg A\). They are logically equivalent.
  • Direct Proof: A method of proving an implication \(P \to Q\) by assuming \(P\) is true and using a chain of direct logical steps to show that \(Q\) must also be true.
  • Proof by Contradiction: An indirect proof technique where one assumes the negation of the desired conclusion and shows that this assumption leads to a logical impossibility.
  • Mathematical Induction: A proof technique used to prove a statement for an infinite set of integers, consisting of a basis step and an inductive step.
  • Basis Step: The first step in an inductive proof, where the statement is shown to be true for the smallest integer value.
  • Inductive Hypothesis: The assumption in an inductive proof that the statement holds true for an arbitrary integer \(k\).
  • Inductive Step: The part of an inductive proof where the statement for \(k+1\) is proven, assuming the inductive hypothesis for \(k\).

3. Formulas

  • Contrapositive Equivalence: \(A \to B \equiv \neg B \to \neg A\)
  • Biconditional Equivalence: \(A \leftrightarrow B \equiv (A \to B) \& (B \to A)\)
  • Definition of an Odd Integer: \(n = 2k + 1\)
  • Definition of an Even Integer: \(n = 2k\)
  • Sum of First \(n\) Integers: \[ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \]
  • Sum of First \(n\) Squares: \[ \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \]
  • Sum of a Geometric Series: \[ \sum_{i=0}^{n} 2^i = 2^{n+1} - 1 \]
  • Fibonacci Recurrence Relation: \(f_n = f_{n-1} + f_{n-2}\)
  • Binet’s Formula: \[ f_n = \frac{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}} \]
  • Bernoulli’s Inequality: \((1 + x)^n \ge 1 + xn\)

4. Examples

4.1. Use a Direct Proof (Lab 5, Task 1)

Use a direct proof to show that the sum of two odd integers is even.

Click to see the solution
  1. Assume the premise: Let x and y be two arbitrary odd integers.
  2. Use the definition of odd integers: An integer is odd if it can be expressed in the form 2k + 1 for some integer k. Therefore, we can write:
    • x = 2a + 1
    • y = 2b + 1 (where a and b are integers).
  3. Calculate the sum:
    • x + y = (2a + 1) + (2b + 1) = 2a + 2b + 2.
  4. Show the result matches the definition of an even integer: An integer is even if it can be written as 2k. We can factor out a 2 from the sum:
    • x + y = 2(a + b + 1).
  5. Conclusion: Since a and b are integers, (a + b + 1) is also an integer. Thus, the sum is 2 times an integer, which proves that the sum of two odd integers is even.
Answer: The proof demonstrates that the sum of two odd integers can always be expressed in the form 2k, which is the definition of an even number.
4.2. Use a Direct Proof (Lab 5, Task 1.a)

Use a direct proof to show that the product of two odd numbers is odd.

Click to see the solution
  1. Assume the premise: Let x and y be two arbitrary odd integers.
  2. Use the definition of odd integers: We can write x = 2a + 1 and y = 2b + 1 for some integers a and b.
  3. Calculate the product:
    • x ⋅ y = (2a + 1)(2b + 1) = 4ab + 2a + 2b + 1.
  4. Show the result matches the definition of an odd integer: We can factor out 2 from the first three terms:
    • x ⋅ y = 2(2ab + a + b) + 1.
  5. Conclusion: Let k = (2ab + a + b). Since a and b are integers, k is also an integer. The product is in the form 2k + 1, which proves that the product of two odd numbers is odd.
Answer: The proof shows that the product can be expressed in the form 2k + 1, which is the definition of an odd number.
4.3. Prove a Biconditional Statement (Lab 5, Task 1.b)

Prove that if n is a positive integer, then n is even if and only if 7n + 4 is even.

Click to see the solution

To prove a biconditional statement (if and only if), we must prove the implication in both directions.

  1. Part 1: Prove that if n is even, then 7n + 4 is even.
    • Assume n is even. By definition, n = 2k for some integer k.
    • Substitute this into the expression: 7(2k) + 4 = 14k + 4.
    • Factor out a 2: 2(7k + 2).
    • Since 7k + 2 is an integer, the expression 2(7k + 2) is even. This direction is proven.
  2. Part 2: Prove that if 7n + 4 is even, then n is even.
    • We will use proof by contraposition. The contrapositive statement is: If n is odd, then 7n + 4 is odd.
    • Assume n is odd. By definition, n = 2k + 1 for some integer k.
    • Substitute this into the expression: 7(2k + 1) + 4 = 14k + 7 + 4 = 14k + 11.
    • Rewrite the expression: 14k + 10 + 1 = 2(7k + 5) + 1.
    • Since 7k + 5 is an integer, the expression 2(7k + 5) + 1 is odd.
    • Since the contrapositive is true, the original implication is true.
Answer: Because the implication holds true in both directions, the “if and only if” statement is proven.
4.4. Prove a Biconditional Statement (Lab 5, Task 1.c)

Prove that if n is a positive integer, then n is odd if and only if 5n + 6 is odd.

Click to see the solution

We must prove the implication in both directions.

  1. Part 1: Prove that if n is odd, then 5n + 6 is odd.
    • Assume n is odd, so n = 2k + 1 for some integer k.
    • Substitute into the expression: 5(2k + 1) + 6 = 10k + 5 + 6 = 10k + 11.
    • Rewrite the expression to fit the odd definition: 10k + 10 + 1 = 2(5k + 5) + 1.
    • This is in the form 2m + 1, so 5n + 6 is odd. This direction is proven.
  2. Part 2: Prove that if 5n + 6 is odd, then n is odd.
    • We use proof by contraposition. The contrapositive is: If n is even, then 5n + 6 is even.
    • Assume n is even, so n = 2k for some integer k.
    • Substitute into the expression: 5(2k) + 6 = 10k + 6.
    • Factor out a 2: 2(5k + 3).
    • This is in the form 2m, so 5n + 6 is even.
    • Since the contrapositive is true, the original implication is true.
Answer: Since both directions of the implication are true, the biconditional statement is proven.
4.5. Use a Proof by Contradiction (Lab 5, Task 2)

Using the contradiction proof method, prove that √2 is irrational.

Click to see the solution
  1. Assume the opposite: Assume that √2 is rational.
  2. Use the definition of a rational number: If √2 is rational, it can be written as a fraction a/b, where a and b are integers, b ≠ 0, and the fraction is in its simplest form (a and b are coprime).
  3. Manipulate the equation:
    • √2 = a/b => 2 = a²/b² => a² = 2b².
  4. Deduce properties:
    • From a² = 2b², we know a² is even. This implies that ‘a’ must also be even.
    • If ‘a’ is even, we can write a = 2k for some integer k.
    • Substituting this back: (2k)² = 2b² => 4k² = 2b² => b² = 2k².
    • This means b² is even, which implies that ‘b’ must also be even.
  5. Find the contradiction: We have concluded that both a and b are even. This means they share a common factor of 2. This contradicts our initial assumption that a/b was in its simplest form.
  6. Conclusion: The assumption that √2 is rational leads to a logical contradiction, so it must be false.
Answer: Therefore, √2 must be irrational.
4.6. Use a Proof by Contradiction (Lab 5, Task 2.a)

Using the contradiction proof method, prove that if n is an integer and n³ + 5 is odd, then n is even.

Click to see the solution
  1. Assume the opposite: Assume that n³ + 5 is odd AND n is odd.
  2. Use the definition of odd: If n is odd, we can write n = 2k + 1 for some integer k.
  3. Substitute and simplify:
    • n³ + 5 = (2k + 1)³ + 5
    • = (8k³ + 12k² + 6k + 1) + 5
    • = 8k³ + 12k² + 6k + 6
  4. Show the result is even:
    • Factor out a 2: 2(4k³ + 6k² + 3k + 3).
    • This shows that if n is odd, then n³ + 5 must be an even number.
  5. Find the contradiction: This contradicts our premise that n³ + 5 is odd.
  6. Conclusion: The assumption that n is odd must be false.
Answer: Therefore, if n³ + 5 is odd, n must be even.
4.7. Use a Proof by Contradiction (Lab 5, Task 2.b)

Using the contradiction proof method, prove that if n is an integer and 3n + 2 is even, then n is even.

Click to see the solution
  1. Assume the opposite: Assume that 3n + 2 is even AND n is odd.
  2. Use the definition of odd: If n is odd, we can write n = 2k + 1 for some integer k.
  3. Substitute and simplify:
    • 3n + 2 = 3(2k + 1) + 2
    • = 6k + 3 + 2 = 6k + 5
  4. Show the result is odd:
    • Rewrite the expression: 6k + 4 + 1 = 2(3k + 2) + 1.
    • This shows that if n is odd, then 3n + 2 must be an odd number.
  5. Find the contradiction: This contradicts our premise that 3n + 2 is even.
  6. Conclusion: The assumption that n is odd must be false.
Answer: Therefore, if 3n + 2 is even, n must be even.
4.8. Use a Proof by Contradiction (Lab 5, Task 2.c)

Using the contradiction proof method, prove that if a, b are integers then a² − 4b ≠ 2.

Click to see the solution
  1. Assume the opposite: Assume that a² − 4b = 2 for some integers a and b.
  2. Manipulate the equation:
    • a² = 4b + 2
    • a² = 2(2b + 1)
  3. Deduce properties:
    • The equation shows that a² is an even number (since it is 2 times an integer).
    • If a² is even, then ‘a’ itself must be even. So, we can write a = 2k for some integer k.
  4. Substitute and simplify:
    • (2k)² = 4b + 2
    • 4k² = 4b + 2
    • Divide the entire equation by 2: 2k² = 2b + 1.
  5. Find the contradiction: The left side of the equation, 2k², is an even number. The right side of the equation, 2b + 1, is an odd number. An even number can never be equal to an odd number.
  6. Conclusion: The initial assumption that a² − 4b = 2 leads to a contradiction.
Answer: Therefore, the statement a² − 4b ≠ 2 must be true for all integers a, b.
4.9. Use a Proof by Mathematical Induction (Lab 5, Task 3)

Prove by mathematical induction that \(1 + 2 + \dots + n = \frac{n(n+1)}{2}\) for any \(n \geq 1\).

Click to see the solution
  1. Base Case (n=1): We verify the formula for the first possible value.
    • LHS = 1.
    • RHS = \(\frac{1(1+1)}{2} = 1\).
    • Since LHS = RHS, the base case holds.
  2. Inductive Hypothesis: Assume the formula is true for some arbitrary integer \(k \geq 1\).
    • Assume: \(1 + 2 + \dots + k = \frac{k(k+1)}{2}\).
  3. Inductive Step: Prove the formula is true for n = k+1, using the hypothesis.
    • We want to prove: \(1 + \dots + k + (k+1) = \frac{(k+1)((k+1)+1)}{2}\).
    • Start with the LHS: \((1 + 2 + \dots + k) + (k+1)\).
    • Substitute the hypothesis: \(\frac{k(k+1)}{2} + (k+1)\).
    • Find a common denominator: \(\frac{k(k+1) + 2(k+1)}{2}\).
    • Factor out (k+1): \(\frac{(k+1)(k+2)}{2}\).
    • This matches the desired RHS, \(\frac{(k+1)((k+1)+1)}{2}\).
  4. Conclusion: By the principle of mathematical induction, the formula is true for all integers \(n \geq 1\).
Answer: The formula is proven true for all \(n \geq 1\).
4.10. Use a Proof by Mathematical Induction (Lab 5, Task 3.a)

Prove by mathematical induction that \(1 + 2^1 + 2^2 + \dots + 2^n = 2^{n+1} - 1\).

Click to see the solution

Let the statement be P(n). The sum is \(\sum_{i=0}^{n} 2^i\).

  1. Base Case (n=0):
    • LHS = \(2^0 = 1\).
    • RHS = \(2^{0+1} - 1 = 2 - 1 = 1\).
    • The base case is true.
  2. Inductive Hypothesis: Assume P(k) is true for some arbitrary integer \(k \geq 0\).
    • Assume: \(1 + 2 + \dots + 2^k = 2^{k+1} - 1\).
  3. Inductive Step: Prove P(k+1) is true.
    • We want to prove: \(1 + \dots + 2^k + 2^{k+1} = 2^{(k+1)+1} - 1\).
    • LHS = \((1 + 2 + \dots + 2^k) + 2^{k+1}\).
    • Substitute the hypothesis: \((2^{k+1} - 1) + 2^{k+1}\).
    • Combine terms: \(2 \cdot 2^{k+1} - 1 = 2^{k+2} - 1\).
    • This is the same as the desired RHS, \(2^{(k+1)+1} - 1\).
  4. Conclusion: The formula is true for all integers \(n \geq 0\).
Answer: By induction, the formula is proven true for all \(n \geq 0\).
4.11. Use a Proof by Mathematical Induction (Lab 5, Task 3.b)

Prove Bernoulli’s inequality by mathematical induction: \((1 + x)^n \geq 1 + xn\) for all \(n \geq 1\), where \(1+x \geq 0\).

Click to see the solution
  1. Base Case (n=1):
    • LHS = \((1 + x)^1 = 1 + x\).
    • RHS = \(1 + (1)x = 1 + x\).
    • \(1+x \geq 1+x\) is true. The base case holds.
  2. Inductive Hypothesis: Assume the inequality holds for some arbitrary integer \(k \geq 1\).
    • Assume: \((1 + x)^k \geq 1 + kx\).
  3. Inductive Step: Prove the inequality holds for n = k+1.
    • We want to prove: \((1 + x)^{k+1} \geq 1 + (k+1)x\).
    • Start with the LHS: \((1 + x)^{k+1} = (1 + x)^k (1 + x)\).
    • Since \(1+x \geq 0\), we can multiply both sides of the hypothesis by \((1+x)\) without changing the inequality direction:
      • \((1 + x)^k (1 + x) \geq (1 + kx)(1 + x)\).
    • Expand the right side: \(1 + x + kx + kx^2 = 1 + (k+1)x + kx^2\).
    • Since \(k \geq 1\) and \(x^2 \geq 0\), the term \(kx^2\) is non-negative (\(kx^2 \geq 0\)).
    • Therefore, \(1 + (k+1)x + kx^2 \geq 1 + (k+1)x\).
    • By transitivity, we have \((1+x)^{k+1} \geq 1+(k+1)x\).
  4. Conclusion: The inequality is true for all integers \(n \geq 1\).
Answer: Bernoulli’s inequality is proven true for all \(n \geq 1\).
4.12. Use a Proof by Mathematical Induction (Lab 5, Task 3.c)

Prove by mathematical induction that \(4^n > 3^n + 2^n\) for all \(n \geq 2\).

Click to see the solution
  1. Base Case (n=2):
    • LHS = \(4^2 = 16\).
    • RHS = \(3^2 + 2^2 = 9 + 4 = 13\).
    • \(16 > 13\) is true. The base case holds.
  2. Inductive Hypothesis: Assume the inequality holds for some arbitrary integer \(k \geq 2\).
    • Assume: \(4^k > 3^k + 2^k\).
  3. Inductive Step: Prove the inequality holds for n = k+1.
    • We want to prove: \(4^{k+1} > 3^{k+1} + 2^{k+1}\).
    • LHS = \(4 \cdot 4^k\).
    • Using the hypothesis: \(4 \cdot 4^k > 4 \cdot (3^k + 2^k) = 4 \cdot 3^k + 4 \cdot 2^k\).
    • Rewrite the result: \(3 \cdot 3^k + 3^k + 2 \cdot 2^k + 2 \cdot 2^k = 3^{k+1} + 3^k + 2^{k+1} + 2^{k+1}\).
    • We know that for \(k \geq 2\), \(3^k > 0\) and \(2^{k+1} > 0\). Therefore, \(3^{k+1} + 3^k + 2^{k+1} + 2^{k+1} > 3^{k+1} + 2^{k+1}\).
    • By transitivity, \(4^{k+1} > 3^{k+1} + 2^{k+1}\).
  4. Conclusion: The inequality is true for all integers \(n \geq 2\).
Answer: The inequality is proven true for all \(n \geq 2\).
4.13. Use a Proof by Mathematical Induction (Lab 5, Task 3.d)

Prove by mathematical induction that \(4^n - 1\) is divisible by 3 for all n.

Click to see the solution
  1. Base Case (n=1):
    • \(4^1 - 1 = 3\). 3 is divisible by 3. The base case is true.
  2. Inductive Hypothesis: Assume the statement is true for some arbitrary integer \(k \geq 1\).
    • Assume: \(4^k - 1\) is divisible by 3. This means \(4^k - 1 = 3m\) for some integer m, or \(4^k = 3m + 1\).
  3. Inductive Step: Prove the statement is true for n = k+1.
    • We want to show that \(4^{k+1} - 1\) is divisible by 3.
    • \(4^{k+1} - 1 = 4 \cdot 4^k - 1\).
    • Substitute the hypothesis (\(4^k = 3m + 1\)): \(4(3m + 1) - 1\).
    • Simplify: \(12m + 4 - 1 = 12m + 3\).
    • Factor out a 3: \(3(4m + 1)\).
    • Since \(4m+1\) is an integer, the expression is a multiple of 3.
  4. Conclusion: The statement is true for all integers n.
Answer: By induction, \(4^n - 1\) is divisible by 3 for all n.
4.14. Use a Proof by Mathematical Induction (Lab 5, Task 3.e)

Prove by mathematical induction that \(5^n - 4n + 15\) is divisible by 16 for all \(n \geq 0\).

Click to see the solution
  1. Base Case (n=0):
    • \(5^0 - 4(0) + 15 = 1 - 0 + 15 = 16\). 16 is divisible by 16. The base case is true.
  2. Inductive Hypothesis: Assume the statement is true for some arbitrary integer \(k \geq 0\).
    • Assume: \(5^k - 4k + 15\) is divisible by 16. This means \(5^k - 4k + 15 = 16m\) for some integer m.
  3. Inductive Step: Prove the statement is true for n = k+1.
    • We want to show that \(5^{k+1} - 4(k+1) + 15\) is divisible by 16.
    • \(5^{k+1} - 4k - 4 + 15 = 5 \cdot 5^k - 4k + 11\).
    • From the hypothesis, we can express \(5^k\) as \(16m + 4k - 15\).
    • Substitute this into the expression: \(5(16m + 4k - 15) - 4k + 11\).
    • Simplify: \(80m + 20k - 75 - 4k + 11 = 80m + 16k - 64\).
    • Factor out 16: \(16(5m + k - 4)\).
    • Since \(5m+k-4\) is an integer, the expression is a multiple of 16.
  4. Conclusion: The statement is true for all integers \(n \geq 0\).
Answer: By induction, \(5^n - 4n + 15\) is divisible by 16 for all \(n \geq 0\).
4.15. Draw a Conclusion (Tutorial 5, Task 1)

What is the conclusion of the following statements?

  • If it’s raining today, we need to take an umbrella.
  • It’s raining today.
Click to see the solution
  1. Identify the premises: Let P be the statement “it’s raining today” and Q be the statement “we need to take an umbrella”. The premises are given in the form P → Q and P.
  2. Apply the rule of inference: This structure matches the rule of inference known as Modus Ponens. This rule states that if an implication (P → Q) is true and its premise (P) is true, then its conclusion (Q) must also be true.
  3. State the conclusion: Based on Modus Ponens, the logical conclusion is Q.
Answer: We need to take an umbrella.
4.16. Draw a Conclusion (Tutorial 5, Task 2)

What is the conclusion of the following statements?

  • If George does not have eight legs, then he is not a spider.
  • George is a spider.
Click to see the solution
  1. Identify the premises: Let P be “George does not have eight legs” and Q be “he is not a spider”. The first premise is P → Q. The second premise, “George is a spider,” is the negation of Q (¬Q).
  2. Apply the rule of inference: This structure matches the rule of inference known as Modus Tollens. This rule states that if an implication (P → Q) is true and its conclusion is false (¬Q), then its premise must also be false (¬P).
  3. State the conclusion: The conclusion is ¬P. The negation of “George does not have eight legs” is “George has eight legs.”
Answer: George has eight legs.
4.17. Draw a Conclusion (Tutorial 5, Task 3)

What is the conclusion of the following statements for Bob, a student in this class?

  • Each of the 93 students in this class owns a personal computer. (∀x ∈ Cl)PC(x)
  • Everyone who owns a personal computer can use a word processing program. (∀x(PC(x) → WP(x)))
Click to see the solution
  1. Identify the premises:
    • Premise 1: For any student x in this class, x owns a personal computer.
    • Premise 2: For any person x, if x owns a personal computer, then x can use a word processing program.
  2. Apply Universal Instantiation: From Premise 1, since Bob is a student in this class, we can conclude that “Bob owns a personal computer.”
  3. Apply Modus Ponens: Premise 2 provides a rule: If PC(x) then WP(x). From the previous step, we know that for Bob, PC(Bob) is true. Therefore, by Modus Ponens, we can conclude that WP(Bob) is true.
Answer: Bob can use a word processing program.
4.18. Use a Direct Proof (Tutorial 5, Task 4)

Use a direct proof to show that the sum of two odd integers is even.

Click to see the solution
  1. Assume the premise: Let x and y be two arbitrary odd integers.
  2. Use the definition of odd integers: An integer is odd if it can be written in the form 2k + 1 for some integer k. Therefore, we can write x = 2a + 1 and y = 2b + 1, where a and b are integers.
  3. Calculate the sum: Add the expressions for x and y:
    • x + y = (2a + 1) + (2b + 1) = 2a + 2b + 2.
  4. Show the sum matches the definition of an even integer: An integer is even if it can be written as 2k for some integer k. Factor out a 2 from the sum:
    • x + y = 2(a + b + 1).
  5. Conclusion: Since a and b are integers, (a + b + 1) is also an integer. Thus, the sum x + y is 2 times an integer, which proves that the sum of two odd integers is always even.
Answer: The proof shows that the sum can be expressed as 2k, which is the definition of an even number.
4.19. Use a Proof by Contraposition (Tutorial 5, Task 5)

Prove that if n is an integer and 3n + 2 is odd, then n is odd.

Click to see the solution
  1. State the contrapositive: A statement “if P, then Q” is logically equivalent to its contrapositive, “if not Q, then not P”.
    • Original statement (P → Q): If (3n + 2 is odd), then (n is odd).
    • Contrapositive (¬Q → ¬P): If (n is not odd), then (3n + 2 is not odd).
    • This is the same as: If n is even, then 3n + 2 is even.
  2. Assume the premise of the contrapositive: Assume n is an even integer.
  3. Use the definition of an even integer: We can write n = 2k for some integer k.
  4. Substitute and simplify: Substitute n = 2k into the expression 3n + 2:
    • 3(2k) + 2 = 6k + 2.
  5. Show the result matches the definition of an even integer: Factor out a 2:
    • 2(3k + 1).
  6. Conclusion: Since k is an integer, 3k + 1 is also an integer. The expression 2(3k + 1) is 2 times an integer, which means 3n + 2 is even. We have successfully proven the contrapositive.
Answer: Since the contrapositive statement is true, the original statement is also proven to be true.
4.20. Use a Proof by Contradiction (Tutorial 5, Task 6)

Using the contradiction proof method, prove that √2 is irrational.

Click to see the solution
  1. Assume the opposite is true: We start by assuming that √2 is rational.
  2. Use the definition of a rational number: If √2 is rational, then it can be written as a fraction a/b where a and b are integers, b ≠ 0, and the fraction is in its simplest form (a and b have no common factors other than 1).
  3. Manipulate the equation: From √2 = a/b, we can square both sides to get 2 = a²/b², which rearranges to a² = 2b².
  4. Deduce properties:
    • Since a² = 2b², a² must be an even number. If a square is even, the number itself must be even. So, ‘a’ is even.
    • If ‘a’ is even, we can write it as a = 2k for some integer k.
    • Substitute this into the previous equation: (2k)² = 2b² → 4k² = 2b² → 2k² = b².
    • This means b² is also an even number, which in turn means that ‘b’ must be even.
  5. Identify the contradiction: We have shown that both ‘a’ and ‘b’ must be even. This means they share a common factor of 2. This contradicts our initial assumption that the fraction a/b was in its simplest form.
  6. Conclusion: The initial assumption that √2 is rational must be false.
Answer: The assumption that √2 is rational leads to a logical contradiction, therefore the statement that √2 is irrational must be true.
4.21. Use a Proof by Mathematical Induction (Tutorial 5, Task 7)

Prove by mathematical induction that \(1 + 2 + \dots + n = \frac{n(n+1)}{2}\) for any \(n \geq 1\).

Click to see the solution
  1. Base Case: We first show the formula is true for the smallest value, n = 1.
    • LHS (Left-Hand Side) = 1.
    • RHS (Right-Hand Side) = \(\frac{1(1+1)}{2} = \frac{2}{2} = 1\).
    • Since LHS = RHS, the base case is true.
  2. Inductive Hypothesis: Assume the formula holds for an arbitrary integer \(k \geq 1\).
    • Assume: \(1 + 2 + \dots + k = \frac{k(k+1)}{2}\).
  3. Inductive Step: We must now prove that the formula also holds for the next integer, n = k+1.
    • We want to show: \(1 + 2 + \dots + k + (k+1) = \frac{(k+1)((k+1)+1)}{2}\).
    • Start with the LHS: \((1 + 2 + \dots + k) + (k+1)\).
    • Using the inductive hypothesis, substitute the sum in the parenthesis: \(\frac{k(k+1)}{2} + (k+1)\).
    • Combine the terms with a common denominator: \(\frac{k(k+1) + 2(k+1)}{2}\).
    • Factor out the common term (k+1): \(\frac{(k+1)(k+2)}{2}\).
    • This matches the simplified RHS: \(\frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2}\).
  4. Conclusion: Because the base case is true and the inductive step has been proven, the formula is true for all integers \(n \geq 1\).
Answer: The formula is proven true for all integers \(n \geq 1\) by the principle of mathematical induction.
4.22. Use a Proof by Mathematical Induction (Tutorial 5, Task 8)

Prove by mathematical induction that \(1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}\) for any \(n \geq 1\).

Click to see the solution
  1. Base Case: Show the formula is true for n = 1.
    • LHS = \(1^2 = 1\).
    • RHS = \(\frac{1(1+1)(2(1)+1)}{6} = \frac{1 \cdot 2 \cdot 3}{6} = 1\).
    • The base case is true.
  2. Inductive Hypothesis: Assume the formula is true for an arbitrary integer \(k \geq 1\).
    • Assume: \(1^2 + 2^2 + \dots + k^2 = \frac{k(k+1)(2k+1)}{6}\).
  3. Inductive Step: Prove that the formula holds for n = k+1.
    • We want to show: \(1^2 + \dots + k^2 + (k+1)^2 = \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}\).
    • LHS = \((1^2 + 2^2 + \dots + k^2) + (k+1)^2\).
    • Substitute the hypothesis: \(\frac{k(k+1)(2k+1)}{6} + (k+1)^2\).
    • Factor out (k+1): \((k+1) \left[ \frac{k(2k+1)}{6} + (k+1) \right]\).
    • Simplify the expression inside the brackets: \((k+1) \left[ \frac{2k^2+k+6k+6}{6} \right] = (k+1) \left[ \frac{2k^2+7k+6}{6} \right]\).
    • Factor the quadratic: \((k+1) \left[ \frac{(k+2)(2k+3)}{6} \right]\).
    • This is the same as the RHS: \(\frac{(k+1)(k+2)(2(k+1)+1)}{6}\).
  4. Conclusion: The formula is true for all integers \(n \geq 1\).
Answer: The formula is proven true for all integers \(n \geq 1\) by mathematical induction.
4.23. Binet’s Formula for Fibonacci Numbers (Tutorial 5, Task 9)

The formula is shown as \(f_n = \frac{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}\)

Click to see the solution
  1. Identify the formula: The given expression is known as Binet’s Formula.
  2. Purpose: It is a closed-form expression for finding the nth term of the Fibonacci sequence (\(f_n\)), where the sequence is defined by \(f_0 = 0\), \(f_1 = 1\), and \(f_n = f_{n-1} + f_{n-2}\).
  3. Significance: This formula is remarkable because it allows direct calculation of any Fibonacci number without needing to compute all the previous numbers in the sequence. It connects the integer sequence to the irrational number \(\sqrt{5}\) and the golden ratio \(\phi = \frac{1+\sqrt{5}}{2}\).
Answer: This is Binet’s formula, which provides a direct method to calculate the nth Fibonacci number.
4.24. Use a Proof by Mathematical Induction (Tutorial 5, Task 10)

Prove by mathematical induction that the sum of the first n Fibonacci numbers with odd indices is given by \(f_1 + f_3 + \dots + f_{2n-1} = f_{2n}\) for any \(n \geq 1\).

Click to see the solution
  1. Base Case: Show the formula is true for n = 1.
    • LHS = \(f_{2(1)-1} = f_1 = 1\).
    • RHS = \(f_{2(1)} = f_2 = 1\).
    • The base case is true.
  2. Inductive Hypothesis: Assume the formula is true for an arbitrary integer \(k \geq 1\).
    • Assume: \(f_1 + f_3 + \dots + f_{2k-1} = f_{2k}\).
  3. Inductive Step: Prove that the formula holds for n = k+1.
    • We want to show: \(f_1 + f_3 + \dots + f_{2k-1} + f_{2(k+1)-1} = f_{2(k+1)}\).
    • LHS = \((f_1 + f_3 + \dots + f_{2k-1}) + f_{2k+1}\).
    • Substitute the hypothesis: \(f_{2k} + f_{2k+1}\).
    • By the recursive definition of the Fibonacci sequence, \(f_m + f_{m+1} = f_{m+2}\).
    • Therefore, \(f_{2k} + f_{2k+1} = f_{2k+2}\).
    • This is equal to the RHS, since \(f_{2(k+1)} = f_{2k+2}\).
  4. Conclusion: The formula is true for all integers \(n \geq 1\).
Answer: By the principle of mathematical induction, the sum of the first n Fibonacci numbers with odd indices is equal to the Fibonacci number with index 2n.